﻿#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

#define MAX(a, b) (a > b ? a : b)

/**
 * 以 arr[index] 结尾的最长递增子序列的长度是多少?
 */
static int recur(const int* arr, const size_t arrSize, int index)
{
	if (index == 0)
	{
		return 1;
	}

	int max = 0;
	for (int i = index - 1; i >= 0; i--)
	{
		if (arr[index] > arr[i])
		{
			int prev = recur(arr, arrSize, i);
			max = MAX(max, prev);
		}
	}

	return max + 1;
}

static int* dp = nullptr;

static int byStrictTable(const int* arr, const size_t arrSize, int index)
{
	if (!dp)
	{
		dp = (int*)malloc(arrSize * sizeof(int));
		memset(dp, 0, arrSize * sizeof(int));

		dp[0] = 1;
		for (int i = 1; i < arrSize; i++)
		{
			int max = 0;
			for (int j = i - 1; j >= 0; j--)
			{
				if (arr[i] > arr[j])
				{
					int prev = dp[j];
					max = MAX(max, prev);
				}
			}

			dp[i] = max + 1;
		}
	}

	return dp[index];
}

/**
 * 以 arr[index] 结尾的最长递增子序列的长度是多少? 并记录这个子序列都有哪些数字
 */
static int recur_NoteNumbers(const int* arr, const size_t arrSize, int index, vector<int>& vec)
{
	if (index == 0)
	{
		vec.push_back(arr[index]);
		return 1;
	}

	int max = 0;
	vector<int> tmpVec;
	vector<int> tmpVec2;
	for (int i = index - 1; i >= 0; i--)
	{
		if (arr[index] > arr[i])
		{
			tmpVec.clear();
			int prev = recur_NoteNumbers(arr, arrSize, i, tmpVec);
			if (max < prev)
			{
				tmpVec2.clear();
				max = prev;
				for (auto it = tmpVec.begin(); it != tmpVec.end(); it++)
				{
					tmpVec2.push_back(*it);
				}
			}
		}
	}

	for (auto it = tmpVec2.begin(); it != tmpVec2.end(); it++)
	{
		vec.push_back(*it);
	}
	
	vec.push_back(arr[index]);

	return max + 1;
}

static unordered_map<int, vector<int>> vecMap;

static int byStrictTable_NoteNumbers(const int* arr, const size_t arrSize, int index, vector<int>& upNumbers)
{
	if (!dp)
	{
		dp = (int*)malloc(arrSize * sizeof(int));
		memset(dp, 0, arrSize * sizeof(int));
		vecMap.clear();

		dp[0] = 1;
		
		vector<int> vec;
		vec.push_back(arr[0]);
		vecMap[0] = vec;

		for (int i = 1; i < arrSize; i++)
		{
			int max = 0;
			vec.clear();
			for (int j = i - 1; j >= 0; j--)
			{
				if (arr[i] > arr[j])
				{
					int prev = dp[j];
					if (max < prev)
					{
						max = prev;
						auto prevVec = vecMap[j];
						vec.clear();
						for (auto it = prevVec.begin(); it != prevVec.end(); it++)
						{
							vec.push_back(*it);
						}
					}
				}
			}

			dp[i] = max + 1;
			vec.push_back(arr[i]);
			vecMap[i] = vec;
		}
	}

	upNumbers = vecMap[index];
	return dp[index];
}

/**
 * 最长递增子序列
 * 比如：[3,1,2,6,3,4,0], 它的最长递增子序列是: [1,2,3,4]
 *
 * 思路:
 * 设原数组为arr，声明一个额外的数组dp和一个额外数组ends，大小和arr一致。
 * dp[i]->子序列以arr[i]结尾的情况下，最长递增子序列的长度。
 * ends一开始所有的元素都无效，假如i位置有效了，那
 * ends[i]->所有长度为i+1的递增子序列中的最小结尾是什么。
 *
 * 1. 处理arr[0]:
 * arr:  [3,1,2,6,3,4,0]
 * dp:   [1,X,X,X,X,X,X]
 * ends: [3,X,X,X,X,X,X]
 *
 * 2. 处理arr[1]:
 * 在ends中找>1的最左的位置，是ends[0], 则用1更新ends[0],
 * 在ends中找小于等于1的数有几个，1个，故dp[1]=1
 * arr:  [3,1,2,6,3,4,0]
 * dp:   [1,1,X,X,X,X,X]
 * ends: [1,X,X,X,X,X,X]
 *
 * 3. 处理arr[2]:
 * 在ends中找>2的最左的位置，没有找到，则扩充ends的有效范围，ends[1]=2
 * 在ends中找小于等于2的数有几个，2个，故dp[2]=2
 * arr:  [3,1,2,6,3,4,0]
 * dp:   [1,1,2,X,X,X,X]
 * ends: [1,2,X,X,X,X,X]
 *
 * 4. 处理arr[3]:
 * 在ends中找>6的最左的位置，没有找到，则扩充ends的有效范围，ends[2]=6
 * 在ends中找小于等于6的数有几个，3个，故dp[3]=3
 * arr:  [3,1,2,6,3,4,0]
 * dp:   [1,1,2,3,X,X,X]
 * ends: [1,2,6,X,X,X,X]
 *
 * 5. 处理arr[4]:
 * 在ends中找>3的最左的位置，是ends[2], 更新ends[2]=3
 * 在ends中找小于等于3的数有几个，3个，故dp[4]=3
 * arr:  [3,1,2,6,3,4,0]
 * dp:   [1,1,2,3,3,X,X]
 * ends: [1,2,3,X,X,X,X]
 *
 * 6. 处理arr[5]:
 * 在ends中找>4的最左的位置，没有找到。则扩充ends的有效范围, ends[3]=4
 * 在ends中找小于等于4的数有几个，4个，故dp[5]=4
 * arr:  [3,1,2,6,3,4,0]
 * dp:   [1,1,2,3,3,4,X]
 * ends: [1,2,3,4,X,X,X]
 *
 * 7. 处理arr[6]:
 * 在ends中找>0的最左的位置，是ends[0], 更新ends[0]=0
 * 在ends中找小于等于0的数有几个，1个，故dp[6]=1
 * arr:  [3,1,2,6,3,4,0]
 * dp:   [1,1,2,3,3,4,1]
 * ends: [0,2,3,4,X,X,X]
 *
 * ends具有单调递增特性，故dp在ends中查找<=arr[i]是非常快的。
 * 最后求解的答案，即为dp中各元素的最大值。
 *
 */
int main_LongestIncrementalSubSequence()
{
	int numbers[] = { 50,40,41,46,43,47,48,20,21,53,58 };
	int count = sizeof(numbers) / sizeof(int);
	
	int maxUpNumberCount = 0;
	for (int i = 0; i < count; i++)
	{
		//int upNumberCount = recur(numbers, count, i);
		int upNumberCount = byStrictTable(numbers, count, i);
		maxUpNumberCount = MAX(maxUpNumberCount, upNumberCount);
	}

	if (dp)
	{
		free(dp);
		dp = nullptr;
	}

	printf("%d\n", maxUpNumberCount);

	maxUpNumberCount = 0;
	int maxIndex = 0;

	/*unordered_map<int, vector<int>> vecMap;
	for (int i = 0; i < count; i++)
	{
		vector<int> vec;
		int upNumberCount = recur_NoteNumbers(numbers, count, i, vec);
		vecMap[i] = vec;
		if (upNumberCount > maxUpNumberCount)
		{
			maxIndex = i;
			maxUpNumberCount = upNumberCount;
		}
	}*/

	maxUpNumberCount = 0;
	for (int i = 0; i < count; i++)
	{
		vector<int> vec;
		int upNumberCount = byStrictTable_NoteNumbers(numbers, count, i, vec);
		if (maxUpNumberCount < upNumberCount)
		{
			maxUpNumberCount = upNumberCount;
			maxIndex = i;
		}

	}

	printf("up sub numbers: ");
	for (auto it = vecMap[maxIndex].begin(); it != vecMap[maxIndex].end(); it++)
	{
		printf("%d ", *it);
	}

	printf("\n");

	if (dp)
	{
		free(dp);
		dp = nullptr;
	}

	printf("use ends:\n");

	int* dpArr = (int*)malloc(count * sizeof(int));
	memset(dpArr, 0, count * sizeof(int));
	int* ends = (int*)malloc(count * sizeof(int));
	memset(ends, 0, count * sizeof(int));

	int validEndsIndex = 0;
	dpArr[0] = 1;
	ends[0] = numbers[0];
	int max = 0;

	for (int i = 1; i < count; i++)
	{
		int cur = numbers[i];
		bool foundEnd = false;
		for (int j = 0; j <= validEndsIndex; j++)
		{
			if (ends[j] > cur)
			{
				ends[j] = cur;
				foundEnd = true;
				break;
			}
		}

		if (foundEnd)
		{

		}
		else
		{
			ends[++validEndsIndex] = cur;
		}

		for (int j = validEndsIndex; j >= 0; j--)
		{
			if (cur >= ends[j])
			{
				dpArr[i] = j + 1;
				break;
			}
		}

		if (dpArr[i] > max)
		{
			max = dpArr[i];
		}
	}

	printf("%d\n", max);

	return 0;
}